package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/flip-equivalent-binary-trees/description
 * ```
 * 951. 翻转等价二叉树
 * 我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。
 * 只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转 等价 于二叉树 Y。
 * 这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是翻转 等价 的树，则返回 true ，否则返回 false 。
 *
 * 示例 1：
 * 输入：root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
 * 输出：true
 * 解释：我们翻转值为 1，3 以及 5 的三个节点。
 *
 * 示例 2:
 * 输入: root1 = [], root2 = []
 * 输出: true
 *
 * 示例 3:
 * 输入: root1 = [], root2 = [1]
 * 输出: false
 *
 * 提示：
 * 每棵树节点数在 [0, 100] 范围内
 * 每棵树中的每个值都是唯一的、在 [0, 99] 范围内的整数
 * ```
 */
class leetcode_951 {
    @Test
    fun test_1() {
        var root1: TreeNode? = null
        run {
            val n1 = TreeNode(1)
            val n2 = TreeNode(2)
            val n3 = TreeNode(3)
            val n4 = TreeNode(4)
            val n5 = TreeNode(5)
            val n6 = TreeNode(6)
            val n7 = TreeNode(7)
            val n8 = TreeNode(8)
            root1 = n1
            n1.left = n2
            n1.right = n3

            n2.left = n4
            n2.right = n5

            n3.left = n6

            n5.left = n7
            n5.right = n8
        }

        var root2: TreeNode? = null
        run {
            val n1 = TreeNode(1)
            val n2 = TreeNode(2)
            val n3 = TreeNode(3)
            val n4 = TreeNode(4)
            val n5 = TreeNode(5)
            val n6 = TreeNode(6)
            val n7 = TreeNode(7)
            val n8 = TreeNode(8)
            root2 = n1
            n1.left = n3
            n1.right = n2

            n3.right = n6

            n2.left = n4
            n2.right = n5

            n5.left = n8
            n5.right = n7
        }
        val actual = flipEquiv(root1, root2)
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val root1: TreeNode? = null
        val root2: TreeNode? = null
        val actual = flipEquiv(root1, root2)
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_3() {
        val root1: TreeNode? = null
        val root2: TreeNode? = TreeNode(1)
        val actual = flipEquiv(root1, root2)
        val expected = false
        Assert.assertEquals(expected, actual)
    }

    private fun flipEquiv(root1: TreeNode?, root2: TreeNode?): Boolean {
        /**
        题型：二叉树的前序遍历
        思路：
        https://leetcode.cn/problems/flip-equivalent-binary-trees/solutions/3766963/jian-jie-dai-ma-fen-xiang-by-fengzil-kxq1
        有以下情况：
        情况1: 均为空，则true
        情况2: 只有一个空，则false
        情况3: 均不空，但值不等，则false
        情况4: 均不空，但值等，继续判读左右子树.
        当不反转与反转有一种情况满足，则是翻转等价 。
        当不反转时：左与左，右与右比较均为true
        当反转时：左与右，右与左比较均为true

        时间复杂度：O(N)
        空间复杂度：O(N)

         */

        // 1 确定函数返回值以及参数
        // 2 确定终止条件
        // Case 1 ： 1 空， 2 空
        if(null == root1 && null == root2){
            return true
        }
        // Case 2 ： 1 非空，2 空
        if(null != root1 && null == root2){
            return false
        }

        // Case 3 ： 1 空，  2 非空
        if(null == root1 && null != root2){
            return false
        }

        if(null != root1 && null != root2){
            // Case 4 ： 1 非空，2 非空，值不等
            if(root1.`val` != root2.`val`){
                return false
            }

            // Case 5 ： 1 非空，2 非空，值等，继续判断左右子树.
            // 3 确定单层递归的处理逻辑: 前序遍历
            // TODO:反转和不反转有一种情况满足就可以。
            // 判断不反转：左与左，右与右比较
            val isValid = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)
            // 判断反转：左与右，右与左比较
            val isValid2 = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left)
            return isValid || isValid2
        }
        return false
    }
}